Smoking remains the number one preventable cause of morbidity and mortality in this nation (CDC, 1997b; McGinnis & Foege, 1993). Moreover, the prevalence of smoking has not declined in the past few years (CDC, 1999b), despite a number of effective and cost-effective smoking cessation programs. One promising method of improving cessation outcomes is to increase physical activity levels in smokers who are trying to quit. Smokers who engage in regular exercise report more confidence in their ability to quit than sedentary smokers (King et al., 1996). There is evidence from randomized controlled trials that adding exercise to cessation programs increases quit rates and helps to reduce post-cessation weight gain (Marcus et al., 1999; Ussher et al., 2000). Previous trials, however, have relied entirely on highly structured, supervised vigorous intensity activity, and have been plagued by difficulty recruiting participants and poor long-term adherence to exercise regimens. Furthermore, these trials generally have had low long-term quit rates, which likely is due at least partly to not including pharmacological intervention (e.g., nicotine replacement). If physical activity is to have a role in smoking cessation, it appears that it will need to be better adapted to increase its acceptability and be integrated into state-of-the-art, combined behavioral/pharmacological cessation programs. With that introduction, we propose the following specific aims: (1) To recruit a cohort of 400 sedentary or minimally active cigarette smokers and randomize them to one of two treatment arms: either a validated, low cost smoking cessation program, or the same smoking cessation program with a physical activity intervention; and (2) To determine the relative efficacy of these two interventions out to a 12-month follow-up. The primary endpoint of the trial is smoking cessation, and secondary endpoints include physical activity level, body mass index, percent body fat, and waist circumference.